1. Field of Invention
Embodiments of the invention relate, in general, to bus arbitration in a network of devices. More specifically, embodiments of the invention relate to multi-port bus arbiters.
2. Description of the Background Art
In network architecture, a bus is a subsystem that transfers data between various connected device nodes. The device nodes may be devices such as Central Processing Units (CPU), Direct Memory Access (DMA) controllers, etc. The bus logically connects the device nodes over a single set of wires. Further, one device node can transfer data over the bus at a point of time. Transfer of data is termed as a transaction. With regard to the transaction over the bus, time is divided into clock cycles called bus cycles that synchronize the bus operations. The device node has to send a request and receive a bus grant from a bus-control mechanism to perform the transaction.
In busy systems, a number of device nodes often simultaneously request the bus grant. In such a case, a control mechanism called bus arbitration has to decide upon the device node that gets the bus grant. Bus arbitration is a technique that selects one device node out of a number of requesting device nodes and grants bus cycles to that particular device node. Bus arbitration is based on a bus arbitration algorithm. The bus arbitration algorithm selects one device node to which the bus will be granted. Arbitration criteria used to make a grant decision can include priority of a device, priority of a data packet, byte count, number of bytes per second, and so forth. The time taken to make a single bus arbitration decision is termed as an arbitration cycle.
Various bus arbitration algorithms are being used for arbitration applications. One existing algorithm takes a single criterion input from each device node that is requesting the bus grant. In case more than one device node provides an identical value of the criterion to create more than one identical-priority requests at the same time, a simple round-robin is employed as a tie-breaker to grant bus cycles. Another existing algorithm uses more than one criterion from each device node requesting the bus grant. However, increase in the number of criteria and the number of device nodes in the system leads to complexity in the algorithm. Therefore, implementation of the bus arbitration algorithm becomes difficult.
One of the existing techniques described in the US patent publication 20030188065 is based on a binary tree concept. The algorithm relies on nodes in the binary tree to forward arbitration decisions along tree branches up to the root of the binary tree. The root signifies the one device node that is selected by the algorithm to receive the bus grant. However, each node has to indicate a flag for the selection of a left or a right branch of the node. The flag indication is based on the probability of priority of the left and right branches. The probability is based on several decision criteria clustered together. In general, priority of request, which may be one of the decision criteria, has only two levels, high and low. Moreover, consideration of multiple priorities leads to queuing up of lower priority requests for long durations. Further, the priority values are limited. They cannot be varied across a range of values. The device node that is selected at the completion of the arbitration has to be informed regarding its selection by a downward traversal of the binary tree. This technique takes into account an increase in the number of device nodes as well as decision criteria. However, as the complexity of the algorithm increases, more processing power is required to implement the technique. Moreover, hardware cost also increases in proportion to the complexity of the algorithm.